A proposition is a declarative sentence that is either true or false but not both
A atomic proposition is a simple statement, one that is not a combination of simpler statements
A compound proposition is a proposition, made up of two or more proposition joined by logical connective operators
logical connective operators: ¬∧∨→↔
Truth Table for the negation of a Proposition
p
¬p
T
F
F
T
Truth Table for the Conjunction of Two Proposition
This is the And condition
p
q
p∧q
T
T
T
F
T
F
T
F
F
F
F
F
Truth Table for the Disjunction of Two Proposition
This is the inclusive OR condition
p
q
p∨q
T
T
T
F
T
T
T
F
T
F
F
F
Exclusive OR
This is the exclusive OR condition
p
q
p⊕q
T
T
F
F
T
T
T
F
T
F
F
F
Conditional Statements
Let p and q be propositions. The conditional statement p→q is the proposition if p, then q The conditional statement p→q is false when p is true and q is false, and true otherwise. In the conditional statement p→q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).
p→q is a conditional statement or a implicationq is true on the condition that q holds to put more bluntly: only when p is true, but q is false is the statement p→q completely incorrect
"if it is raining, then the ground is wet."
"when it is not raining, then the state of the ground is doesn't matter we call this the vacuous case."
Definitions
Proposition
: p→q A conditional statement
: "if it is raining, then the ground is wet"
Converse bdg-dangernot necessarily equivalent to the original proposition
: q→p is the converse of p→q
: > "if the ground is wet, then it is raining"
: "it could be wet for other reasons other than rain"
Inverse bdg-dangernot necessarily equivalent to the original proposition
: ¬p→¬q is the inverse of p→q
: > "if it is not raining, then the ground is not wet"
: "ground could be either wet or dry without rain"
Contrapositive bdg-infoequivalent to the original proposition
: ¬q→¬p is the contrapositive of p→q
: > " if the ground is not wet, then it is not raining "
: "because if it were raining then the ground will be wet"
Equivalent
: When two propositional statement have the same truth value
Conditional
Converse
Contrapositive
Inverse
pq
p→q
q→p
¬q→¬p
¬p↔¬q
T T
T
T
T
T
T F
F
T
F
T
F T
T
F
T
F
F F
T
T
T
T
Biconditionals
The biconditional statementp↔q is the statement p if and only if also called bi-implication
p
q
p↔q
T
T
T
F
T
F
T
F
F
F
F
T
Precedence of Logical Operators
In compound propositions the order of precedence that we calculate is from left to right below
We see that AND circuits are basically serialized and OR circuits are parallel
Note how p∧(p∨q)≡p≡p∨(p∧q) this is called the absorption law
Fuzzy Logic
Used in artificial intelligence
It means 1 for truth and 0 for false but there could be degrees between these two values for example 0.7 for Bill is happy means that it is usually true
Propositional Equivalence
pq¬p¬q
p→q
¬q→¬p
(p→q)↔(¬p→¬q)
1 1 0 0
1
1
1
1 0 0 1
0
0
1
0 1 1 0
1
1
1
0 0 0 1
1
1
1
Note that (p→q)↔(¬p→¬q) is true in all cases it's a tautology
This is becuase (p→q)≡(¬p→¬q)
p∨¬p is always true hence tautology and p∧¬p is always false hence contradiction
Lecturer's example
Let Q(x,y):x2+y2=1
Let D1=R2=\set(x,y)∣x,y∈R all real numbers
D2=S1=\set(x,y)∈R2∣x=cosθ,y=sinθ,0⩽θ<2π The unit circle in R2 centered at the origin
D3=\set(n,n)∈Z2∣n∈Z=diag(Z2)
diagonal subspace of Z2
Then lets evaluate the three DomainsD1,D2,D3D1:for all real numbers there are some that don’t work∀(x,y)∈D1,Q(x,y)isF∃(x,y)∈D1,Q(x,y)isTD2:this domain encompasses all values that work with unit circle∀(x,y)∈D2,Q(x,y)isT∃(x,y)∈D2,Q(x,y)isTD3:this domain encompasses all values that don’t work∀(x,y)∈D3,Q(x,y)isF∃(x,y)∈D3,Q(x,y)isFQ(n,n)=n2+n2=2n2=1iffn2=1/2∴n=±1/2n∈/D3
Quantifiers Over Finite Domains
Say the elements of a domain are x1,x2,...,xn where n is a positive integer then:
∀xP(x)≡P(x1)∧P(x2)∧...∧P(xn)
Or in other words the universal quantification is the same as the conjunction
∃xP(x)≡P(x1)∨P(x2)∨...∨P(xn)
Or in other words the existential quantification is the same as the disjunction
Quantifiers Over Restricted Domains
The statement ∀x<0(x2>0) means "That for every negative real number the square of the negative real number is positive"
Binding Variables
When a quantifier is used on a variable say on x, we say the occurrence of the variable is bound the converse is that the variable is free
Scope
: The part of a logical expression to which a quantifier is applied
Example
Statement: ∃x(x+1=1), so the variable x is bound by the existential quantification ∃x whilst the variable y is free because it not bound by a quantifier and no value is assigned to this variable
Statement: ∃x(P(x)∧Q(x))∨∀xR(x), all the variables are bound
the scope of the first quantifier ∃x is the expression P(x)∧Q(x) because ∃x is applied only to P(x)∧Q(x) and not the rest of the statement
the scope of the second quantifier ∀x is the expression R(x) because ∀x is applied only to R(x) and not the rest of the statement
Logical Equivalence with Quantifiers
Show that ∀x(P(x)∧Q(x)) and ∀xP(x)∧∀xQ(x) are equivalent Assume the use of the same domain
if ∀x(P(x)∧Q(x)) is true, then ∀xP(x)∧∀xQ(x) is true
Suppose that ∀x(P(x)∧Q(x)) is true
This means if a is in domain then P(a)∧Q(a) is true
if ∀xP(x)∧∀xQ(x) is true, then ∀x(P(x)∧Q(x)) is true
bdg-dangercheck textbook solution to this is very wordy
Negating Quantified Expressions
Take Statement "Every student in class has taken a course in calculus" we can denote this as ∀P(x)
Say there does exist a student that hasn't taken calculus then you see we get the statement that
¬(∀xP(x))≡∃x¬P(x)
Take the negation of the statement like "Every student in class has not taken a course in calculus" denoted as ∀x¬P(x) this would be equivalent to statement "There does not exist a student who has taken a course in calculus" hence another get another equivalence
¬(∃xP(x))≡∀x¬P(x)
Nested Quantifiers
∀x∃y(x+y=0)
which is the same thing as ∀xQ(x),
where Q(x) is ∃yP(x,y),
where P(x,y)isx+y=0\
bdg-whiteexample 1 Assume that the domain for the variables x and y consists of all real numbers bdg-secondaryStatement∀x∀y(x+y=y+x) bdg-infosays∀x∀y(x+y=y+x)
Negating
bdg-primaryNegating Nested Quantifiers
Let the universe of discourse be R bdg-secondaryConsider Proposition∀x∃y(xy=1) bdg-infoin wordsfor all x∈R, there is a y∈R such that xy=1
Translate these statements into English, where the domain for each variable consists of all real numbers.
a) ∀x∃y(x < y) For all x there exists a y such that x < y
b) ∀x∀y(((x ≥ 0) ∧ (y ≥ 0)) → (xy ≥ 0)) For all x there are all y such that x greater or equal than 0 and y is greater or equal to 0 then the product of x and y is greater or equal than 0
c) ∀x∀y∃z(xy = z) For all x and for all y there exists a z such that product of x and y is equal to z
7 Let T(x, y) mean that student x likes cuisine y, where the
domain for x consists of all students at your school and
the domain for y consists of all cuisines. Express each of
these statements by a simple English sentence.
a) ¬T(Abdallah Hussein, Japanese) Abdullah Hussein does not like Japanese cuisine
b) ∃xT(x, Korean) ∧ ∀xT(x, Mexican) There exists a student at my school who like Korean and all students at my school like Mexican
c) ∃y(T(Monique Arsenault, y) ∨ T(Jay Johnson, y)) There exists a cuisine that Monique Arsenault likes or Jay Johnson like a that cuisine
d) ∀x∀z∃y((x ≠ z) → ¬(T(x, y) ∧ T(z, y))) For all students at my school and another group of people who are not students a my school there exists a cuisine where it is untrue That a student and a non-student loves
e) ∃x∃z∀y(T(x, y) ↔ T(z, y)) there exists a student at my school and a z proposition for all cuisines where th student and thier favourite cuisine is true if and only if the z condition has the likes
f ) ∀x∀z∃y(T(x, y) ↔ T(z, y))
25 Translate each of these nested quantifications into an En-
glish statement that expresses a mathematical fact. The
domain in each case consists of all real numbers.
a) ∃x∀y(xy = y) There exists a x for every y such that the product of x and y is yx=1
b) ∀x∀y(((x < 0) ∧ (y < 0)) → (xy > 0)) for all x and all y if x is greater than 0 and y is negative then x times y is greater than 0
c) ∃x∃y((x^2 > y) ∧ (x < y)) there exists a x and there exists a y such that the square of x is greater than y and x is less than y
d) ∀x∀y∃z(x + y = z) there exists a x and there exists a y and there exists a z such that x plus y is equal to z
27 Determine the truth value of each of these statements
if the domain of each variable consists of all real num-
bers.
a) ∀x∃y(x^2 = y) T
b) ∀x∃y(x = y^2 ) T
c) ∃x∀y(xy = 0) T for y = 0
d) ∃x∃y(x + y ≠ y + x) F\ supposed to be false
e) ∀x(x ≠ 0 → ∃y(xy = 1)) T
f) ∃x∀y(y ≠ 0 → xy = 1) T
g) ∀x∃y(x + y = 1) T for negative numbers
h) ∃x∃y(x + 2y = 2 ∧ 2x + 4y = 5) T
i) ∀x∃y(x + y = 2 ∧ 2x − y = 1) T
x = 2 -y
2(2 -y) − y = 1
4 - 2y = 1
j) ∀x∀y∃z(z = (x + y)∕2) T
30 .Rewrite each of these statements so that negations ap-
pear only within predicates (that is, so that no negation
is outside a quantifier or an expression involving logical
connectives).
a) ¬∃y∃xP(x, y)
b) ¬∀x∃yP(x, y)
c) ¬∃y(Q(y) ∧ ∀x¬R(x, y))
d) ¬∃y(∃xR(x, y) ∨ ∀xS(x, y))
e) ¬∃y(∀x∃zT(x, y, z) ∨ ∃x∀zU(x, y, z))
31 Express the negations of each of these statements so that
all negation symbols immediately precede predicates.
a) ∀x∃y∀zT(x, y, z)
b) ∀x∃yP(x, y) ∨ ∀x∃yQ(x, y)
c) ∀x∃y(P(x, y) ∧ ∃zR(x, y, z))
d) ∀x∃y(P(x, y) → Q(x, y))
32 Express the negations of each of these statements so that
all negation symbols immediately precede predicates.
a) ∃z∀y∀xT(x, y, z)
b) ∃x∃yP(x, y) ∧ ∀x∀yQ(x, y)
c) ∃x∃y(Q(x, y) ↔ Q(y, x))
d) ∀y∃x∃z(T(x, y, z) ∨ Q(x, y))
33 Rewrite each of these statements so that negations ap-
pear only within predicates (that is, so that no negation
is outside a quantifier or an expression involving logical
connectives).
a) ¬∀x∀yP(x, y)
b) ¬∀y∃xP(x, y)
c) ¬∀y∀x(P(x, y) ∨ Q(x, y))
d) ¬(∃x∃y¬P(x, y) ∧ ∀x∀yQ(x, y))
e) ¬∀x(∃y∀zP(x, y, z) ∧ ∃z∀yP(x, y, z))
40 Find a counterexample, if possible, to these universally
quantified statements, where the domain for all variables
consists of all integers.
a) ∀x∃y(x = 1∕y)
b) ∀x∃y(y 2 − x < 100)
c) ∀x∀y(x 2 ≠ y 3 )
45 Determine the truth value of the statement ∀x∃y(xy = 1)
if the domain for the variables consists of
a) the nonzero real numbers.
b) the nonzero integers.
c) the positive real numbers.\
Rules of Inference
Proofs
: In mathematics these are validarguments that establish the truth of a mathematical statement
Arguments
: A sequence of statements that end with a conclusion
Valid
: The conclusion or final statement of the arguments follows from the truth of the preceding statements or premises of the arguments
Rules of Inferences
: These are the templates or basic tools for establishing the truth of statements
Fallacies
: Incorrect reasoning that may lead to incorrect conclusions
Lemma
: a simple theorem
Corollary
: A direct result of the theorem (special case etc)
Conjecture
: A statement whose truth value is unknown
Argument Form
Consider the following arguments which by definition is a sequence of propositions
"If you have access to the internet, then you can change your grade" "You have access to the network" therefore "You can change your grade"
(p→q)∧p→qit’s a tautology
So a argument is a proposition of the form
p1∧p2∧p3∧...∧pn→q
Propositions
: are what p1∧p2∧p3∧...∧pn called
Hypothesis
: is what q is called
Above is what defines being a valid argument meaning all the premises are true so the conclusion follows as well because it means the hypothesis is true or when the statement is a tautology
Rules of Inference
Modus Ponens
Modus Tolens
Hypothetical Syllogism
Disjunctive Syllogism
Resolution
Let us examine it
p∨q≡¬p→q¬p∨r≡¬p→r
Start with proposition p
if it is true then we conclude r\
if it is false then we conclude q the proposition p leads to q or r
Rules of Inference for Quantified Statements
Universal Instantiation
Universal Generalization
Existential Instantiation
Existential Generalization
Mathematical Proofs
Axioms or Postulates
: statements that are assumed to be true used in proofs
We consider 5 types of proofs
Direct Proof - show p→q is true
Indirect Proof - prove that the contrapositive ¬q→¬p is true
also called proof by contra position
Proof by contradiction - To prove pt show ¬p→F is true
Proof by cases
Proof of Equivalences
Direct Proof
The implication p→q can be proved to be true by showing that if p is true then q is true
This means the combination of p≡T or q≡F never occurs
Example
bdg-primary-linetheoremif n is an even integer, then n3 is an even integer
bdg-secondary-lineproofbdg-plaindirect
Let n be an even integer. Then by definition, ∃k∈Z such that n=2k
Now: n3=(2k)3=23k3=2(4k3) Since, 4k3∈Z, we have n3 an even integer
bdg-primary-linetheoremif n is an odd, then n2−n is an even
bdg-secondary-lineproofbdg-plaindirect
Let n be an odd. Then by definition, ∃k∈Z such that n=2k=1
Now: n2−n=(2k+1)2−(2k+1)=4k2+4k+1−2k−1=4k2+2k=2(2k2+k) Since, 2k2+k∈Z, we have n2−n is even
bdg-danger-lineaxiom Assume the fact that 3n is even iff n even bdg-primary-linetheoremn is an even integer iff 3n + 5 is odd
bdg-secondary-lineproofbdg-plaindirect
Let n be an odd. Then by definition, ∃k∈Z such that n=2k=1
Now: n2−n=(2k+1)2−(2k+1)=4k2+4k+1−2k−1=4k2+2k=2(2k2+k) Since, 2k2+k∈Z, we have n2−n is even
Indirect Proof
Proof by Contradiction
Proof by Cases
In this method proves theorems of the form P=(p1∨p2∨...∨pn)→q
We prove that pi→q,∀i=1,2,3,...,n and use the tautology
(p1∨p2∨...∨pn)↔[(p1→q)∨...∨(pn→q)]
Proof of Equivalences
Here we show everything is equivalent we could use a circle of implications